/**
 * Date: 2019/2/23
 * Time: 21:23
 * User: Driss.
 *
 * 线性排序：桶排序，计数排序，基排序
 */
public class LinearSort {


    /**
     * 计数排序：当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。
     * @param a
     * @param n
     */
    public static void countingSort(int[] a,int n){

        //查找数组中的数据范围
        int max = a[0];
        for (int i = 0; i < n; i++) {
            if(max < a[i])
                max = a[i];
        }

        //申请一个计数数组c，大小为max+1
        int[] c = new int[max + 1];
        for (int i = 0; i <=  max; i++) {
            c[i] = 0;
        }

        // 计算每个元素的个数，放入 c 中
        for (int i = 0; i < n; i++) {
            c[a[i]]++;
        }

        // 依次累加
        for (int i = 1; i <= max; ++i) {
            c[i] = c[i-1] + c[i];
        }

        // 临时数组 r，存储排序之后的结果
        int[] r = new int[n];

        // 计算排序的关键步骤，有点难理解
        for (int i = n - 1; i >= 0; --i) {
            int index = c[a[i]]-1;
            r[index] = a[i];
            c[a[i]]--;
        }

        // 将结果拷贝给 a 数组
        for (int i = 0; i < n; ++i) {
            a[i] = r[i];
        }

    }


    public static void main(String[] args) {

    }
}
